1. Field of the Invention
The present invention generally relates to computer graphics. More particularly, the present invention relates to software and hardware accelerated display of vector graphics data.
2. Discussion of the Related Art
Advances in video processing technology have enabled real time display of complex moving images using commercially available computer hardware. Applications of such video processing technology include computer games, video content downloaded over the internet, music videos displayed on personal digital devices, and video displayed on cell phones. Further recent advances have enabled 3D graphics to be displayed on computer displays, personal digital devices, and cell phones.
Essential to the advance of video processing technology has been the use of vector graphics data formats in representing images. Representing an image as a set of vectors has not only vastly increased the efficiency in transmitting and storing video data (as opposed to raster scan or bitmap representations), but it has enabled video content to be scalable. Scalability refers to the ability to render an image or video with varying degrees of resolution depending on the display hardware displaying the images or video, and/or on other considerations such as bandwidth. In other words, the resolution of an image displayed on a cell phone will be different from that displayed on a high resolution monitor, and the quality of video streamed via a low bandwidth connection will be different from that streamed via a high bandwidth connection. In any of these cases, vector graphics representation of images or video allows one data format to be used regardless of the display device or bandwidth.
Displaying vector graphics data typically involves converting the data into a plurality of triangles, wherein each triangle has a style (e.g., color), shape, and location. Accordingly, depending on the complexity of the image, this may involve thousands of triangles. Converting vector graphics data into a plurality of triangles is referred to as triangulation, or tessellation. Accordingly, efficiently displaying vector graphics data requires the ability to quickly and reliably tessellate the data.
Many related art approaches to tessellation incur certain disadvantages. First, many related art tessellation algorithms have a computational cost that can vary a great deal depending on the content of the image to be displayed. As a result, they are not suitable for consistent real time use without a separate preprocessing step. Second, certain related art tessellation algorithms are unstable in that an error or anomaly in depicting a small feature can corrupt the displayed image or cause the display device to crash. Third, many related art approaches suffer from problems associated with layered polygons, in which polygons are rendered independently in separate layers. This can lead to what is referred to as the “group opacity” problem, when multiple layers are rendered with varying opacity, as might happen when a multi-layered polygon is meant to fade in a series of images. And finally, related art approaches to vector graphics typically generate polygons independently, so that polygons that have a shared edge are each given separate edges. This can lead to the appearance of seams between rendered polygons. As used herein, a polygon may refer to any figure to be displayed that may be tessellated for the purpose of being rendered on a display device.
The latter three of the above problems may be mitigated by “flattening” the geometry of polygons that are to be displayed. However, related art approaches to tessellation that use multiple layers are ill-suited to geometry flattening. Further, related art approaches typically do not handle “non-simple” cases when processing vector graphics data. Non-simple cases include fully or partially overlapped edges, polygon edges that pass through vertices of edges of other polygons, more than two polygon edges having a shared vertex, and crossing edges (self-intersections).
Accordingly, what is needed is a system and method for processing vector graphics data that flattens the geometry of multiple polygons, provides for polygons having shared edges, handles errors in a stable manner, and is computationally efficient.